<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>
<head>
  <title>Elsa Design</title>
  <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
  <style type="text/css">
    H1 { font-size: 150% }
    H2 { font-size: 125% }
    H3 { font-size: 100% }
    P.title { font-size: 175%; font-weight: bold }
    P.remark { font-size: 125%; color: red }
    SPAN.todo { font-weight: bold }
    SPAN.program { font-family: monospace }
    SPAN.variable { font-family: monospace }
    a.toc:link { text-decoration: none }
    a.toc:visited { text-decoration: none }
  </style>
</head>
<body>

<center>
<p class="title">Elsa Design</p>
<p>By Daniel Wilkerson and Scott McPeak
</center>

<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<h1>Introduction</h1>

<p>This file is an attempt to articulate the design of
<a href="../index.html">Elsa</a>
to someone who would like to work on it.

<p>Elsa attempts to parse C and C++:
<ul>

<li>C++ is defined by the C++03 spec, more officially known as "ISO/IEC
14882:2003: Programming languages -- C++."  You will see it referred to
as "cppstd" in comments throughout the code.  There are also references
to the older C++98 standard.  The standard can be
purchased from <a href="http://www.ansi.org/">ANSI</a> (among other
places), and drafts
of the standard can be found on
<a href="http://www.csci.csusb.edu/dick/c++std/">Dick Botting's page</a>.

<li>C is defined by the C89 and C99 specs, 
"ISO/IEC 9899:1990 Programming languages -- C" and 
"ISO/IEC 9899:1999 Programming languages -- C", respectively.

<li>Elsa also supports the older C syntax described in
    Kernighan and Ritchie's
    <a href="http://cm.bell-labs.com/cm/cs/cbook/">"The C Programming Language"</a>
    ("K&amp;R").

<li>GCC has numerous extensions to C and C++, mostly documented in the
    <a href="http://gcc.gnu.org/onlinedocs/gcc-3.1/gcc/">GCC Manual</a>; Elsa
    parses most of these.

</ul>

<p>Note that Elsa does not try to reject all invalid programs.  The
checking that Elsa does is primarily for the purpose of ensuring that
its interpretation of the code is correct.  For example, Elsa
<em>does</em> check that argument types match parameter types (which
helps to catch bugs in Elsa's type computation logic, and is required
to determine where user-defined conversions take place), but <em>does
not</em> enforce the access control rules ("public", "private", etc.)
of C++.  Ideally, Elsa eventually will check such things, but it is
not a priority for the forseeable future.

<p>Elsa is extensible; that is, one may add additional syntactic
features to the language being parsed, <em>without</em> directly
modifying the files that define the base language.  This
"base-and-extension design pattern" occurs frequently in the design of
Elsa; for example, it is used to support for C99 and GNU extensions to C++.
The intent is to allow users to modify Elsa almost arbitrarily, but still be
able to keep up with the Elsa release cycle.

<p>There are several stages to the processing of an input file:<br>
<center><img src="block_diagram.png" alt="Elsa Block Diagram"></center>
<!-- BEGIN CONTENTS -->
<!-- automatically generated by insert-html-toc; do not edit the TOC directly -->
<ul>
  <li><a class="toc" href="#lexing">1. Lexing</a>
  <ul>
    <li><a class="toc" href="#lexer_build">1.1 Lexer Build Process</a>
    <li><a class="toc" href="#lexer_design">1.2 Lexer Design</a>
  </ul>
  <li><a class="toc" href="#parsing">2. Parsing</a>
  <ul>
    <li><a class="toc" href="#parser_build">2.1 Parser Build Process</a>
    <li><a class="toc" href="#ast_build">2.2 AST Build Process</a>
    <li><a class="toc" href="#parser_actions">2.3 Parser Actions</a>
  </ul>
  <li><a class="toc" href="#typechecking">3. Type Checking</a>
  <ul>
    <li><a class="toc" href="#disambiguation">3.1 AST disambiguation</a>
    <li><a class="toc" href="#lookup">3.2 Variable lookup</a>
    <ul>
      <li><a class="toc" href="#lookup_variables">3.2.1 Variables</a>
      <li><a class="toc" href="#overload_resolution">3.2.2 Overload Resolution</a>
    </ul>
    <li><a class="toc" href="#type_annotation">3.3 Type Annotation</a>
    <li><a class="toc" href="#implicit_conversions">3.4 Insertion of Implicit Conversions</a>
    <li><a class="toc" href="#templates">3.5 Templates</a>
    <ul>
      <li><a class="toc" href="#template_representation">3.5.1 Template Representation</a>
      <li><a class="toc" href="#template_instantiation">3.5.2 Template Instantiation</a>
      <li><a class="toc" href="#dependent_names">3.5.3 Dependent Types and Names</a>
    </ul>
  </ul>
  <li><a class="toc" href="#elaboration_cdtors">4. Elaboration of constructors and destructors</a>
  <li><a class="toc" href="#post_processing">5. Post-processing</a>
  <li><a class="toc" href="#extension">6. Extension Mechanisms</a>
  <ul>
    <li><a class="toc" href="#ext_lexer">6.1 Lexer Extensions</a>
    <li><a class="toc" href="#ext_parser">6.2 Parser Extensions</a>
    <li><a class="toc" href="#ext_tcheck">6.3 Type Checker Extensions</a>
    <li><a class="toc" href="#ext_elaboration">6.4 Elaboration Extensions</a>
    <li><a class="toc" href="#ext_post">6.5 Post-processing Extensions</a>
  </ul>
  <li><a class="toc" href="#correctness">7. Correctness Assurance Techniques</a>
  <ul>
    <li><a class="toc" href="#testing">7.1 Testing</a>
    <ul>
      <li><a class="toc" href="#regrtest">7.1.1 regrtest</a>
      <li><a class="toc" href="#minimization">7.1.2 Minimization</a>
      <li><a class="toc" href="#builtin_functions">7.1.3 Built-in Testing Functions</a>
      <li><a class="toc" href="#large_packages">7.1.4 Running Elsa on large software packages</a>
    </ul>
    <li><a class="toc" href="#debugging">7.2 Debugging</a>
    <ul>
      <li><a class="toc" href="#tracing_flags">7.2.1 Tracing Flags</a>
      <li><a class="toc" href="#data_print">7.2.2 Data structure print routines</a>
    </ul>
    <li><a class="toc" href="#documentation">7.3 Documentation</a>
    <ul>
      <li><a class="toc" href="#doc_external">7.3.1 External Documentation</a>
      <li><a class="toc" href="#doc_internal">7.3.2 Internal Documentation</a>
      <li><a class="toc" href="#doc_doxygen">7.3.3 Why I don't use Documentation Generators</a>
    </ul>
    <li><a class="toc" href="#assertions">7.4 Assertions</a>
    <li><a class="toc" href="#invalid_input">7.5 Invalid C++</a>
  </ul>
</ul>
<!-- END CONTENTS -->



<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="lexing"></a>
<h1>1. Lexing</h1>

<p>Lexing (a.k.a. scanning) is the process of partitioning a flat sequence
of characters into a sequence of <em>tokens</em>.  In addition to being a
partition, the tokens represent <em>classifications</em> of the partitions:
the character sequence "123" might be called an "integer literal", and the
sequence "abc" an "identifier".  The Lexer discards comments and whitespace
(rather than passing them on to the parser).

<a name="lexer_build"></a>
<h2>1.1 Lexer Build Process</h2>

<p>As mentioned above, much of the Elsa design involves extension mechanisms,
and the Lexer is no exception.  A base description is combined with one or
more extension descriptions to arrive at the full lexical language:

<p><center><img src="lexer_build.png" alt="Elsa Lexer Build Process"></center>

<p>
Above, solid lines indicate direct flow, and dashed lines indicate where
one file is <tt>#included</tt> by another (i.e. both directly flow into
a program further down but not shown).  Files are shown in ellipses and
programs are shown in rectangles.

<p><a href="../cc.lex">cc.lex</a> is the base lexer description.  It
is written in the <a href="http://www.gnu.org/software/flex/manual/html_chapter/flex_toc.html">Flex</a>
language.  <a href="../gnu.lex">gnu.lex</a> is an extension lexer description;
it contains definitions for GNU and C99-specific lexical elements.  These two
descriptions are combined with <a href="../merge-lexer-exts.pl">merge-lexer-exts.pl</a>
to produce <a href="../lexer.lex">lexer.lex</a>.
lexer.lex is subsequently read by Flex to generate
<a href="../lexer.yy.cc">lexer.yy.cc</a>, a C++ module that does the
actual scanning.

<p><b>Build process invariant:</b> Any time a script or tool produces a
text file, the build process marks it read-only.  This makes it harder to
accidentally edit a file that is automatically generated.  Thus, all the
files in the diagram above that are the output of a rectangle are marked
read-only.

<p>Unlike <a href="http://www.gnu.org/software/bison/manual/html_node/index.html">Bison</a>,
<a href="../../elkhound/index.html">Elkhound</a>
does not automatically choose the mapping from lexer token codes
(like "4") to conceptual lexical elements (like "integer literal").  So the
Elsa build process uses a script called
<a href="../make-token-files">make-token-files</a> to assign the mapping.
It uses the token descriptions supplied by
<a href="../cc_tokens.tok">cc_tokens.tok</a> and
<a href="../gnu_ext.tok">gnu_ext.tok</a>.


<a name="lexer_design"></a>
<h2>1.2 Lexer Design</h2>

<p>
<a href="../lexer.lex">lexer.lex</a> specifies how to partition the input
characters into tokens.  Most of the actions are straightforward.  One
tricky point is the notion of "separating tokens" and "nonseparation tokens",
which is explained at the top of <a href="../lexer.cc">lexer.cc</a>.
Another is that "<tt>#line</tt>" directives are handled by recording them
with the <a href="../../smbase/hashline.h">hashline</a> module, which
can then be used to map a raw input source location to a the location designed
by the <tt>#line</tt> directives.

<p>
The <a href="../baselexer.h">baselexer</a> module is responsible for
coordinating the activity of a Flex lexer and an Elkhound parser.  It
inherits from LexerInterface (<a
href="../../elkhound/lexerint.h">lexerint.h</a>), which defines three
fields (<span class="variable">type</span>, <span
class="variable">sval</span>, and <span class="variable">loc</span>) that the Elkhound
parser reads.  BaseLexer updates these fields during lexing according
to what the lexer actions do.

<p>
BaseLexer is extended by the <a href="../lexer.h">lexer</a> module,
which defines the Lexer class, which contains the methods that the
lexer actions invoke.

<p>
If you would like to see the results of just lexing an input file, the
<span class="program">tlexer</span> program (<a href="../tlexer.cc">tlexer.cc</a>) will
read in a preprocessed C/C++ source file and print out the sequence of
tokens that would be yielded to the parser.


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="parsing"></a>
<h1>2. Parsing</h1>

<p>
Parsing is the process of converting a token stream into an Abstract
Syntax Tree (AST).  In Elsa, the AST produced by the parser is not
necessarily a tree at all, but a Directed Acyclic Graph (DAG) in
general, because of ambiguities.  However, we still call it an AST.


<a name="parser_build"></a>
<h2>2.1 Parser Build Process</h2>

<p>
The parser is written in a mixture of <a
href="../../elkhound/index.html">Elkhound</a> and C++; the Elkhound
language defines how terminals, nonterminals and productions are
defined, while the reduction actions associated with the productions
are written in C++.  The parser description is a combination of three
files:
<ul>
<li><a href="../cc_tokens.ids">cc_tokens.ids</a>: assigns token codes
    (automatically produced, as described above)
<li><a href="../cc.gr">cc.gr</a>: base C++ grammar
<li><a href="../gnu.gr">gnu.gr</a>: extensions for gcc and C99
</ul>

<p>
<center><img src="parser_build.png" alt="Elsa Parser Build Process"></center>

<p>
There are three output files from Elkhound:
<ul>
<li><a href="../cc.gr.gen.h">cc.gr.gen.h</a>: declares the CCParse class,
    which has the parser entry point, among other things
<li><a href="../cc.gr.gen.cc">cc.gr.gen.cc</a>: contains definitions of
    CCParse methods, including all of the reduction actions
<li><a href="../cc.gr.gen.out">cc.gr.gen.out</a>: exhaustive description of
    the parsing DFA; mostly of use when debugging shift/reduce conflicts
    (not necessary with Elkhound, but sometimes can improve performance)
</ul>


<a name="ast_build"></a>
<h2>2.2 AST Build Process</h2>

<p>
The AST is described by a language that is input to the
<a href="../../ast/index.html">astgen</a> tool.  The description is
comprised of several files:
<ul>
<li><a href="../cc.ast">cc.ast</a>: base C++ language AST
<li><a href="../cc_tcheck.ast">cc_tcheck.ast</a>: declares AST node methods
    and annotation fields for use by the type checker
<li><a href="../cc_print.ast">cc_print.ast</a>: methods for pretty printing
<li><a href="../cc_elaborate.ast">cc_elaborate.ast</a>: elaboration methods
<li><a href="../gnu.ast">gnu.ast</a>: gcc and C99 extensions to the language AST
<li><a href="../cfg.ast">cfg.ast</a>: methods for computing a control flow graph
    at the statement granularity (<a href="../cfg.h">cfg</a> module)
</ul>

<p>
<center><img src="ast_build.png" alt="Elsa AST Build Process"></center>

<p>
The output files are:
<ul>
<li><a href="../cc.ast.gen.h">cc.ast.gen.h</a>: contains C++ class declarations
    for all of the AST nodes
<li><a href="../cc.ast.gen.cc">cc.ast.gen.cc</a>: definitions of the methods of
    the AST node classes
</ul>


<a name="parser_actions"></a>
<h2>2.3 Parser Actions</h2>

<p>
Most of the parser actions are straightfoward: combine the AST elements
that comprise the production right-hand side (RHS) into a single AST
element that represents the left-hand side (LHS).

<p>
Two issues are explained at the top of <a href="../cc.gr">cc.gr</a> are
the various source of names, and handling of destructive actions.

<p>
Most instances of syntactic ambiguity are handled by using the <span
class="variable">ambiguity</span> fields of certain AST nodes to
explicitly represent the different alternatives.  The type checker
then has the responsibility for picking one alternative.  For example,
the ambiguous syntax "<tt>return (x)(y);</tt>" would be represented as
shown in the following diagram, where the cast interpretation
"<tt>return (x)y;</tt>" is shown in green, and the function call
interpretation "<tt>return x(y);</tt>" is shown in purple.  Note that
the nodes for "<tt>x</tt>" and "<tt>y</tt>" are shared by both
interpretations.

<center><img src="ambiguous_ast.png" alt="Ambiguous AST Example"></center>

<p>
A few instances of ambiguity are handled at parse time, rather than
deferring to the type checker as in the diagram above.  This is done
by writing <span class="variable">keep</span> functions that cancel a
reduction if it can be determined that the syntax giving rise to the
reduction has another (better) interpretation.  For example, there is
an ambiguity in template parameters because "&lt;class T&gt;" could be
a type parameter called "T", or it could be a non-type parameter of
(existing) type "class T" but with no parameter name.  As the Standard
specifies that this is always a type parameter, the reduction for
non-type parameters cancels itself if the type is like "class T" (see
the <tt>TemplateParameter -&gt; ParameterDeclaration</tt> reduction
and the associated <span class="variable">keep</span> function
in <a href="../cc.gr">cc.gr</a>).

<p>The tracing flag "printAST" to <span class="program">ccparse</span>
will print the (possibly ambiguous) AST as it exists before type
checking.

<p>The tracing flag "parseTree" will print the full parse tree.  The
parse tree shows the structure of reduction action calls by replacing
every reduction action with one that builds a generic parse tree node
out of its subtrees.  This is useful for debugging ambiguities, since
it shows exactly what happens in the parser, without interference from
the actual reduction actions.


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="typechecking"></a>
<h1>3. Type Checking</h1>

<p>The type checker (<a href="../cc_tcheck.cc">cc_tcheck.cc</a>) does
five major jobs:
<ul>
  <li><a class="toc" href="#disambiguation">3.1 AST disambiguation</a>
  <li><a class="toc" href="#lookup">3.2 Variable lookup</a>
  <li><a class="toc" href="#type_annotation">3.3 Type Annotation</a>
  <li><a class="toc" href="#implicit_conversions">3.4 Insertion of Implicit Conversions</a>
  <li><a class="toc" href="#templates">3.5 Templates</a>
</ul>

<p>The fundamental data structure on which the type checker does its
work is the AST, documented in <a href="cc.ast.html">cc.ast.html</a>.

<p>The tracing flag "printTypedAST" will print the AST after type
checking.

<a name="disambiguation"></a>
<h2>3.1 AST disambiguation</h2>

<p>
AST disambiguation means choosing a single interpretation for AST
nodes that have more than one (i.e. a non-NULL <span
class="variable">ambiguity</span> field).  Then, the surrounding AST
nodes are modified to reflect the chosen choice and forget about the
others.  The tracing flag "disamb" will report disambiguation
activity.

<p>
Most disambiguation is done by the generic ambiguity resolver,
in <a href="../generic_amb.h">generic_amb.h</a>.  The
<span class="variable">resolveAmbiguity</span> function simply
invokes the type checker recursively on each alternative by
invoking the <span class="variable">mid_tcheck</span> method.
If exactly one alternative successfully type-checks (i.e. does not
report any errors), then that alternative is selected.  The
<span class="variable">ambiguity</span> link for the selected
node is nullified, and the selected node returned so the caller
can update its AST pointer accordingly.  It is an error if more
or less than one alternative type-checks.

<p>
As recursive type checking can sometimes involve doing computations
unrelated to the disambiguation, such as template instantiation,
at certain points the type checker uses the
<span class="variable">InstantiationContextIsolator</span> class
(<a href="../cc_env.h">cc_env.h</a>) to isolate those computations.
They will only be done once (regardless of how many times they
occur in ambiguous alternatives), and any errors generated are
<em>not</em> considered by the ambiguity resolver.

<p>
Not every ambiguous situation will be resolved by the generic
resolver.  In particular, there is a very common ambiguity between
<span class="variable">E_funCall</span> and <span
class="variable">E_constructor</span>, since the parser can almost
never tell when the "<tt>f</tt>" in "<tt>f(1,2,3)</tt>" is a type or a
function.  If the generic procedure were used, this would lead to
exponential type checking time for expressions like
"<tt>f1(f2(f3(...(fN())...)))</tt>".  Since this disambiguation choice
depends only on the function/type and not the arguments, <span
class="variable">Expression::tcheck</span> explicitly checks for this
case and then just checks the first component by invoking the <span
class="variable">inner1_tcheck</span> method.  Once the selection is
made, <span class="variable">inner2_tcheck</span> is invoked to finish
checking th argument list.

<p>
There are a few other ad-hoc disambiguation strategies here and 
there, such as for deciding between statements and declarations, and
resolving uses of implicit int (when K&amp;R support is enabled).


<a name="lookup"></a>
<h2>3.2 Variable lookup</h2>

<p>
Declared entities are represented by Variable objects
(<a href="../variable.h">variable.h</a>).  In general, lookup is
the process of mapping a name (which is a string of characters)
and a context (scopes, etc.) to a Variable.  AST nodes that
contain names subject to lookup, such as
<span class="variable">E_variable</span> or 
<span class="variable">E_fieldAcc</span>, contain
a <span class="variable">var</span> field.  The
<span class="variable">var</span> field is initially NULL, and
the type checker sets it to some non-NULL value once it figures
out which Variable the name refers to.

<p>
Though the C++ standard in principle gives all of the rules for
exactly how lookup should be performed, in practice it can be
difficult to map those rules into an implementation.  The auxilliary
document <a href="lookup.txt">lookup.txt</a> explains how the
rules in the standard are implemented in Elsa.

<a name="lookup_variables"></a>
<h3>3.2.1 Variables</h3>

<p>
There are many kinds of entities represented by Variables, as shown in
the following diagram.  The rectangles and arrows represent a kind of 
inheritance hierarchy; e.g., a Class is one of the type-denoting
Variables (note that this is only conceptual inheritance; in the
implementation, there is just one class called Variable).  The ellipses
are data fields attached to Variables.

<center><img src="variables.png" alt="Kinds of Variables"></center>

<p>
On the left half of the diagram are names corresponding to types, and
on the right half are non-type entities.  Types are introduced by a
<tt>typedef</tt> or by a class declaration.  Non-types are introduced
by a variable declaration, or a function prototype or definition.  A
few oddballs, such as enumerators and namespaces, round out the set.
The neighborhoods of the class and function template boxes are
expanded in a later diagram, below.

<p>                                            
Every Variable has a name (but it might be NULL), a type (only NULL
for namespaces), and some flags.  The name is how the entity is found
by lookup.  The type is either the denoted type (for type entities) or
the type of the variable (for non-types).  The flags say what kind of
entity a given Variable is; by interrogating the flags, one can
determine (for any given Variable object) to which box in the diagram
it belongs.

<p>
It may seem odd that so many kinds of entities are represented with
the same Variable class.  The reason is that all of these entities are
<em>looked up</em> in the same way, and all of these entities' names
hide each other (when scopes are nested), so the Variable is the
fundamental element of a Scope (<a
href="../cc_scope.h">cc_scope.h</a>).  The word "name" in quotes
suggests this connection, as all of these entities correspond to what
the C++ Standard simply calls a "name".

<a name="overload_resolution"></a>
<h3>3.2.2 Overload Resolution</h3>

<p>
In C++, function names and operators can be <em>overloaded</em>,
meaning there is more than one entity with a given name.  The name is
mapped to an entity by considering the context in which it is used:
for a function call, the argument types determine the overloaded
entity; when taking the address of a function, the type of the
variable receiving the address determines which entity has its address
taken; etc.

<p>
Elsa represents overload sets by having a single representative
Variable contain a linked list, the contents of which are the overload
set (including the representative itself).  Initially, typechecking an <span
class="variable">E_variable</span> or <span
class="variable">E_fieldAcc</span> that refers to an overloaded name
will set the node's <span class="variable">var</span> field to point
at the set representative.  Later, it uses the
call site arguments to pick the correct entity.  Then, the
<span class="variable">E_variable</span> or
<span class="variable">E_fieldAcc</span> node's
<span class="variable">var</span> field is modified so that it
points directly at the chosen element.  

<p>
At the moment, there is no way to distinguish between a Variable
object denoting an overloaded set, and a Variable object denoting just
the specific entity that happens to be the set representative, so this
distinction must be inferred by context (i.e. before overload
resolution has occurred, or after it).  This design might be changed
at some point.

<p>
When Elsa finds that an operator is overloaded, it again uses the
arguments to select the proper operator.  If the selected operator
is a built-in operator, the (say) <span class="variable">E_binary</span>
node is left alone.  But if a user-defined operator is chosen, then
the node is changed into an <span class="variable">E_funCall</span> to
reflect that, semantically, a function call occurs at that point.
One way to observe this change is to pretty-print the AST (see
<a href="#prettyprint">pretty printing</a>).


<a name="type_annotation"></a>
<h2>3.3 Type Annotation</h2>

<p>
Expressions (and a few other nodes) have a type associated with them.
The type checker computes this type, and stores it in the
<span class="variable">type</span> field of the node.

<p>
Types themselves have internal structure, which is explained in
<a href="cc_type.html">cc_type.html</a>.


<a name="implicit_conversions"></a>
<h2>3.4 Insertion of Implicit Conversions</h2>

<p>
When an object is (say) passed as an argument to a function, depending
on the types of the argument and parameter, an <em>implicit
conversion</em> may be required to make the argument compatible with
the parameter.  This determination is made by the <a
href="../implconv.h">implconv</a> module.  Among the kinds of implicit
conversions there are <em>user-defined conversions</em>, conversions
accomplished by calling a user-defined function.  When Elsa finds that
user-defined conversion is required, it modifies the AST to reflect
the use of the conversion function, as if it had been written
explicitly.

<p>
<b>Bug</b>: While Elsa currently (2005-05-29) does all the necessary
computation to determine if a user-defined conversion is needed, in
some cases it fails to rewrite the AST accordingly.  This will be
fixed at some point (hopefully soon).


<a name="templates"></a>
<h2>3.5 Templates</h2>

<p>
Elsa does template instantiation for three reasons.  First,
instantiation of template class declarations is required in order to
disambiguate the AST, since a template class member can be either
a type or a variable name, and that affects how a use of that name
is parsed.  
      
<p>
Second, instantiation is required to do annotation such as for
expression types, since the type of an expression involving a member
of a template class is dependent on that template class's definition.

<p>
Finally, instantiation of function templates (including members of
class templates) lets analyses ignore the template (polymorphic)
definitions and concentrate on the (monomorphic) instantiations, which
are usually easier to analyze.

<a name="template_representation"></a>
<h3>3.5.1 Template Representation</h3>

<p>
Function templates are represented with a Variable (<a
href="../variable.h">variable.h</a>) to stand for the function
template, and an associated TemplateInfo (<a
href="../template.h">template.h</a>) structure to remember the
template parameters (including default arguments), and any
instantiations that have been created.

<p>
The TemplateInfo class acts as an extension of the Variable class;
every TemplateInfo is associated with a unique Variable.  It would
have been possible to make TemplateInfo actually inherit from
Variable, and at some point the design may be changed to do just that.

<p>
In the following diagram, rectangles represent (separate) objects that
exist at run-time, and arrows represent pointers among those objects.
An ellipse overlapping several arrows represents a list of pointers.

<center><img src="function_templates.png" alt="Function Template Representation"></center>

<p>
Class templates are also represented by a Variable/TemplateInfo
pair.  The wrinkle is that template classes can have
<em>partial specializations</em>, user-provided classes for use
when the template arguments match some given pattern (for example, a generic
<tt>Vector</tt> template might have a partial specialization for
<tt>Vector&lt;T*&gt;</tt> that uses a more efficient representation):

<center><img src="class_templates.png" alt="Class Template Representation"></center>

<a name="template_instantiation"></a>
<h3>3.5.2 Template Instantiation</h3>

<p>
Function templates are instantiated as soon as a definition and a use
(the use supplying the template arguments) have been seen.  This is
done by calling <span
class="variable">Env::instantiateFunctionTemplate</span>
(<a href="../template.cc">template.cc</a>), which
returns a Variable/TemplateInfo pair that represents the
instantiation.  If the instantiation has already been made, the
existing one is returned.  If not, the template definition AST is
<em>cloned</em> (deeply copied), the template parameters are bound to
their arguments, and the entire definition re-type-checked.

<p>
Class templates are instantiated as soon as a use is seen; a program
is ill-formed if a definition has not been seen by the time of first
use.  Instantiation is done by calling
<span class="variable">Env::instantiateClassTemplate</span>
(<a href="../template.cc">template.cc</a>).  As above, if the
instantiation already exists, it is re-used; otherwise the template
definition is cloned and re-type-checked.

<p>
Function members of class templates are <em>not</em> instantiated
until a use of the member is seen.  For members whose definition appears
"inline" in the class body, the 
<span class="variable">MR_func::f</span> field points at the
<em>uninstantiated</em> template body.  The body will be cloned
and type-checked only when it is instantiated.  One consequence of this
design is that analyses (usually) need to avoid looking at such uninstantiated
members; one way to do this is by using 
<span class="variable">ASTTemplVisitor</span> 
(<a href="../cc_ast_aux.h">cc_ast_aux</a>) to do the traversal, as it
automatically skips such methods.

<a name="dependent_names"></a>
<h3>3.5.3 Dependent Types and Names</h3>

<p>
The C++ Standard has fairly elaborate rules for deciding when a type
or a name in a template definition is <em>dependent</em> on the
template parameters.  Furthermore, it specifies that names and types
that are <em>not</em> dependent <em>must</em> be looked up in the
context of the original template definition, <em>not</em> the
instantiation context (as is the case for dependent names).

<p>
To implement this (and to disambiguate template definition ASTs), Elsa
type-checks function template definitions in advance of any instantiation.
A dependent type is represented by the
<span class="variable">ST_DEPENDENT</span> pseudo-type
(see <span class="variable">enum SimpleTypeId</span> in
<a href="../cc_flags.h">cc_flags.h</a>).

<p>
Furthermore, while type checking the template definition, if a name
lookup is determined to not be dependent, the
<span class="variable">nondependentVar</span> field is set to the
same thing as the
<span class="variable">var</span> field (both are fields of AST nodes
that have names subject to lookup).  Later, when an instantiation
is created, the <span class="variable">nondependentVar</span>
value is preserved by cloning, and used instead of doing a new lookup,
if it is not NULL.

<p>
When a class template instantiation is requested but one or more
arguments is dependent, a
<span class="variable">PseudoInstantiation</span> type
(<a href="../template.h">template.h</a>) is created.  This is more
precise than simply yielding
<span class="variable">ST_DEPENDENT</span>, and that precision is
necessary in some cases, and much cleaner than doing a full
"instantiation" with incomplete information.

<p>
Similarly, when type checking a template definition, the template
type parameters are bound to (unique) instances of
<span class="variable">TypeVariable</span>
(<a href="../template.h">template.h</a>) objects.


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="elaboration_cdtors"></a>
<h1>4. Elaboration of constructors and destructors</h1>

Constructors and destructors: 
<ul>

<li> A struct/class with no ctor gets a no arg ctor that calls the no
arg ctor of its members and superclasses.

<li> A struct/class with no copy ctor gets a one arg copy ctor that
calls the copy ctor for its members and superclasses.

<li> A struct/class with no copy assignment operator gets a one arg
copy assignment operator that calls the copy assignment operator for
its members and superclasses.

<li> A struct/class with no dtor gets a dtor that calls the dtor for
its members and superclasses.

</ul>

<span class="todo">Add more info about this stage.</span>


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="post_processing"></a>
<h1>5. Post-processing</h1>

<p>Elsa will perform various forms of post-processing on request.

<p>Tracing flag "printHierarchies" will print inheritance
hierarchies in Dot format. Interesting in that virtual inheritance is
represented properly; for example <a href="in/std/3.4.5.cc">in/std/3.4.5.cc</a>
yields <a href="gendoc/3.4.5.png">3.4.5.png</a>.

<a name="prettyprint"></a>
<p>Tracing flag "prettyPrint" will print out the AST as C++.  One use
of this feature is to do some analysis on the source code, then print it
out with analysis results intermixed as annotations that can then be
fed to another analysis tool.  <b>Bug:</b> (2005-05-29) Not all C++ 
constructs are correctly printed yet.


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="extension"></a>
<h1>6. Extension Mechanisms</h1>

<p>
Each phase of Elsa has some degree of support for extensions, as
documented in this section.

<p>
First, let me distinguish <em>compile-time</em> extensions
from <em>run-time</em> extensions.  Compile-time extensions let a
programmer add new features to a program without having to modify that
program's original source code; but the program must be recompiled
(possibly with an altered build process) to incorporate those
extensions.  In contrast, run-time extensions can be added by an
end-user without recompilation; browser plugins are an example.

<p>
While Elsa does have a few run-time extension mechanisms such as the
TypeFactory, the majority are compile-time mechanisms.  The rationale
is that I can support a much wider range of extensions that way, and
given that Elsa is more or less intended to be research infrastructure,
there is no compelling reason for run-time extensibility.
Note that the <a href="http://opencxx.sourceforge.net/">OpenC++</a>
parser <em>is</em> designed for run-time extensibility.

<p>
In the limit, one need not explicitly design for compile-time
extensibility at all, since programmers could simply write their
extensions as patch files, and let <tt>patch</tt> incorporate them.
However, this would be far from ideal, since patch files are fragile
in the face of changes to the underlying source, and the toolchain
(compiler error messages, source-level debuggers) would be unaware of
them.  So the general Elsa strategy is to design ways that programmers
can write extensions with the following properties:
<ul>
<li>Self-contained.  An extension should mostly make sense
    in isolation.  (Contrast with a context diff, which contains pieces
    of the code into which the changes are inserted.)
<li>Robust.  If the artifact that is being extended is changed, the
    extension should continue to work (within reason).
<li>Toolchain-aware.  When an extension causes a compiler error message,
    or a debugger steps into code added by an extension, the tool should
    refer to the extension source itself, rather than an intermediate
    file generated by combining the original with extensions.
<li>Powerful.  Extensions should have the power to effect almost any
    change to the original, such that programmers never need to make
    direct changes to the original.
<li>Separate.  The base Elsa system should not need to be aware of any
    particular extension.  (Contrast with sprinkling Elsa with #ifdefs
    for every extension, which otherwise meets the above criteria.)
</ul>

<p>
Unfortunately, not every extension mechanism used in Elsa has all of these
properties.  I will point out which properties hold below.

<a name="ext_lexer"></a>
<h2>6.1 Lexer Extensions</h2>

<p>
New token types can be added by creating a <tt>.tok</tt> file and
arranging to feed it to the
<a href="../make-token-files"><tt>make-token-files</tt></a> script.
The effect of this is simply to define names and aliases for tokens,
such that the lexer and parser can refer to them coherently.
Flaws: not toolchain-aware.
(Example: <a href="../gnu_ext.tok"><tt>gnu_ext.tok</tt></a>)

<p>
New lexical rules can be added by creating a <tt>.lex</tt> file
and arranging to feed it to the
<a href="../merge-lexer-exts.pl"><tt>merge-lexer-exts.pl</tt></a>
script.  This script textually inserts the extension into a combined
flex input file, with extensions coming before the original rules
so as to be able to override them.  Flaws: not toolchain-aware,
cannot delete origial rules (can leave spurious warnings).
(Example: <a href="../gnu.lex"><tt>gnu.lex</tt></a>)

<a name="ext_parser"></a>
<h2>6.2 Parser Extensions</h2>

<p>
New syntactic constructs can be added by creating a <tt>.gr</tt> file
and passing it on the <tt>elkhound</tt> command line.  The new grammar
consists of the union of the productions from the original and the
extension(s).  This is the cleanest of all the extension mechanisms,
having all of the desired extension properties listed above.
(Example: <a href="../gnu.gr"><tt>gnu.gr</tt></a>)

<p>
When new syntactic constructs are introduced, they typically need new
AST nodes to represent them.  New AST nodes can be added by creating a
<tt>.ast</tt> file and passing it on the <tt>astgen</tt> command line.
The effective AST spec is the union of the base and all extensions.
Flaws: <tt>astgen</tt> should emit #line directives that point into
the respective <tt>.ast</tt> files (this is not a flaw with extension
per se, but <tt>astgen</tt> in general).
(Example: <a href="../gnu.ast"><tt>gnu.ast</tt></a>)

<a name="ext_tcheck"></a>
<h2>6.3 Type Checker Extensions</h2>

<p>
New Type classes can be added by creating new subclasses of AtomicType
and Type (<a href="../cc_type.h"><tt>cc_type.h</tt></a>), and implementing 
the appropriate virtual methods.  Operations on the new types can be defined 
by creating a subclass of Env (<a href="../cc_env.h"><tt>cc_env.h</tt></a>)
and overriding some of its methods.  Flaws: not very powerful; you can
only change behaviors for which hooks are already provided.

<p>
Type checking for new AST nodes can be added simply by adding a new
C++ source file that implements the <tt>tcheck</tt> methods for the
new nodes.  Flaws: hard to do context-dependent behaviors.
(Example: <a href="../gnu.cc"><tt>gnu.cc</tt></a>)

<p>
New fields and methods can be added to the Type superclass by replacing
the definition of Type by defining the <tt>TYPE_CLASS_FILE</tt> macro.
See <a href="cc_type.html#basetype">cc_type.html, Section 6</a> for 
more information.  Flaws: can only change the Type class, not others.

<p>
Finally, the plan is to add a generic source code patcher that
operates at a higher level and is more robust than <tt>patch</tt>.
This would let users do things like rename functions, insert snippets
of code into functions, add members to classes, etc.  However, that
mechanism is still quite experimental and so not yet shipped with
Elsa.  Flaws: vaporware.

<a name="ext_elaboration"></a>
<h2>6.4 Elaboration Extensions</h2>

<p>
Elaboration is done by the ElabVisitor class
(<a href="../cc_elaborate.h"><tt>cc_elaborate.h</tt></a>), which
could be extended with the usual inherit-and-override C++ idiom.
See the next section for more information about visitors.

<a name="ext_post"></a>
<h2>6.5 Post-processing Extensions</h2>

<p>
Within Elsa, the intent is that users write new post-processing
analyses and plug them in by simply copying and modifying
<a href="../main.cc"><tt>main.cc</tt></a>.  This gives users
maximal control over how an Elsa-based analysis interacts with
the outside world.  Flaws: ad-hoc.

<p>
Alternatively, the <a href="http://www.cs.berkeley.edu/~dsw/oink.html">Oink</a>
framework (based on Elsa) provides a more systematic architecture
for integrating post-processing analyses, both with Elsa and with
each other.  Flaws: analysis must fit into the framework.

<p>
For implementing an analysis, programmers are of course free to simply
write a custom traversal similar to the type checker
(<a href="../cc_tcheck.cc"><tt>cc_tcheck.cc</tt></a>).  However,
for many analyses it is convenient to extend the ASTVisitor, a class
created automatically by <tt>astgen</tt>.  A simple example is the
NameChecker in <a href="../main.cc"><tt>main.cc</tt></a>, which does
some simple processing at each Expression node.  Note that your visitor
can traverse the full AST by inheriting from ASTVisitor, or traverse
only the "lowered" AST (e.g., skipping templates and only looking at
the instantiations) by inheriting from LoweredASTVisitor
(<a href="../cc_ast_aux.h"><tt>cc_ast_aux.h</tt></a>).
Flaws: visitors are simple, but make context dependence difficult
to achieve.


<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<a name="correctness"></a>
<h1>7. Correctness Assurance Techniques</h1>

<p>
This section explains what policies and procedures are in place to try
to ensure that Elsa is "correct", in the sense that it accepts valid
C++ input code and produces an annotated, elaborated AST that
accurately reflects the syntax and semantics of that code.

<p>
(I do not call this section "Quality Assurance" because I am talking
about procedures followed by developers, rather than the processes
and measurement techniques that might be used after the fact.)

<p>
Most of what is outlined here is standard practice, and the potential
scope of "correctness assurance" is huge, so I'll try to confine this
to things directly relevant to Elsa.

<a name="testing"></a>
<h2>7.1 Testing</h2>

<!--
testing

  - regrtest
    - general procedures
    - every bug yields a new or enhanced testcase
  - ERROR lines
  - minimization
  - special built-in testing functions
  - running Elsa on large software packages
-->

<p>
"Testing" is the process of searching for evidence of a defect.  The
input to testing is a program, and the output is a testcase (for Elsa,
a C++ input file) such that running the program with that testcase
causes the program to demonstrably misbehave.

<a name="regrtest"></a>
<h3>7.1.1 regrtest</h3>

<p>
The central artifact of the Elsa testing effort is the
<a href="../regrtest"><tt>regrtest</tt></a> ("regression test")
script.  This script runs Elsa (via the <tt>ccparse</tt> driver
program) on hundreds of input files, checking that it accepts the
valid inputs and rejects the invalid ones.  In some cases there
are known bugs in Elsa; corresponding inputs are marked with
"failparse" (or similar), and <tt>regrtest</tt> expects Elsa to
fail those tests.  It should be run before every commit.

<p>
Invalid inputs are handled by adding lines of the form
<pre>
  //ERROR(n): some-invalid-syntax
</pre>
to an otherwise valid input file, where <it>n</it> is a small
integer like 1 or 2.  The <a href="../multitest.pl"><tt>multitest.pl</tt></a>
script will run <tt>ccparse</tt> once on the valid input, then
uncomment the ERROR lines and confirm that Elsa now rejects the
input.  Note that the script requires that Elsa not segfault
or abort (e.g., by failing an assertion); it must <em>cleanly</em>
reject the invalid input.

<p>
Ideally, a <tt>regrtest</tt> testcase should have these properties:
<ul>
<li>Small: It should not take Elsa a long time to process the
    testcase, because the total running time of <tt>regrtest</tt>
    should be kept reasonably small, so that it remains convenient
    to use.
<li>Identifiable: Each testcase should be testing some specific
    language feature or combination of features.  By inspecting
    the testcase (including comments) it should be possible to
    identify what is being tested.  This makes it easier to
    debug Elsa when a particular test starts failing.  (It is fine
    if a single testcase file tests many things, as long as each 
    thing is itself identifiable.)
<li>Unique: There should not be another testcase that tests the
    exact same set of features.  Or if there is, the dominating test
    should be testing them in a more complex setting, and come
    <em>after</em> the dominated testcase in <tt>regrtest</tt> so
    that the simple test has a chance to fail first.  This
    helps to debug failing tests, and to keep the running time
    of <tt>regrtest</tt> down.
</ul>

<p>
Of course, these are not absolute rules, but they help to explain
why we don't, say, put the entire preprocessed Mozilla codebase
into <tt>regrtest</tt>.

<p>
Somewhat contradicting the above, at the end of <tt>regrtest</tt>
there are several "big" tests.  These are included both as a sanity
check to make sure Elsa can parse a few big things, and as a
performance test.  However, if a bug in Elsa is revealed by one
of these big tests, a minimized testcase should be added as well
so that we are not unduly relying upon them.

<p>
Moreover, the general procedure is that no Elsa bug should be
fixed without first adding a minimized testcase or extending
an existing testcase.  This has several benefits:
<ul>
<li>It helps to clarify the nature of the problematic syntax.
<li>It makes it much faster to test proposed fixes.
<li>It ensures the bug won't be reintroduced at some point in the
    future (this is the true meaning of "regression" tests).
</ul>

<a name="minimization"></a>
<h3>7.1.2 Minimization</h3>

<p>
The Elsa developers rely heavily on the technique of <em>minimization</em>,
which takes as input a testcase demonstrating an Elsa bug and produces as
output a testcase that demonstrates the same bug but is as small as possible.
This makes debugging easier and faster, and produces better testcases for
inclusion in <tt>regrtest</tt>.

<p>
Typically, minimization is done with respect to two nominally opposing
criteria:
<ul>
<li>The testcase should be <em>good</em>.  For example, gcc accepts it.
    (Note that gcc-3 is a much better measure of goodness than gcc-2 for
    this purpose.)
<li>Elsa reports the testcase as <em>bad</em>.  For example, Elsa incorrectly
    reports an error, or fails an assertion.
</ul>

<p>
We have considerable support for automating the minimization process.
The <a href="http://delta.tigris.org">Delta</a> tool will minimize an
input with respect to arbitrary criteria, and the 
<a href="../test-for-error"><tt>test-for-error</tt></a> script provides
the good/bad criteria above.  The two are combined in the
<a href="../run-delta-loop"><tt>run-delta-loop</tt></a> script.  These
scripts may need to be modified to suit your particular use,
or of course you can write your own.

<p>
Despite the automation, delta typically does not yield inputs that are
adequately minimal.  Usually, I let delta make a first pass, then I
simplify the testcase a bit (by hand) in ways that delta does not know
how, let delta run again, then finish up by hand.  The goal here is to
make it as easy as possible to <em>comprehend</em> the
meaning/semantics of the testcase, so that the person trying to debug
Elsa when that testcase fails has it as easy as possible.

<p>
There are several particular techniques that I have found useful when
doing by-hand minimization after delta has done some work:
<ul>
<li>Remove unused corresponding parameters and arguments.
<li>Use search+replace to eliminate typedefs.
<li>Delete empty base classes (delta will often empty the class, but
    cannot remove the reference in the base class list).
<li>Simplify elements of the statement and expression language, for
    example replacing "<tt>if (x) { foo(); }</tt>" with just "<tt>foo();</tt>".
<li>If template instantiation is involved, use the "-tr template" tracing
    flag to find out what is the <em>last</em> template instantiation
    attempted before the failure.  Then, just put an explicit instantiation
    request for that instantiation at the bottom of the file.  This often
    lets me remove large amounts of code that just served to eventually
    trigger a particular instantiation.
</ul>

<a name="builtin_functions"></a>
<h3>7.1.3 Built-in Testing Functions</h3>

<p>
If all that Elsa were trying to do was recognize valid C++ and reject
invalid C++, then the above techniques would be adequate.  However,
Elsa is also trying to compute an internal representation of the input
that accurately conveys its semantics.  For example, it computes the
type of every expression in the program.  What if that type computation
is incorrect?  It is sometimes possible to leverage a particular incorrect
type computation such that it leads to spurious rejection, but doing so
is ad-hoc and sometimes difficult.

<p>
Another approach would be to dump out the internal representation for
a given source file and then compare that to a "known good" version of
that dump.  The problem with this approach is it is fragile: if the
dump format happens to change, all the known-good dumps have to either
be modified by hand, or discarded and regenerated (possibly accidentally
saving wrong output in the process, if there is an unnoticed bug).

<p>
The Elsa solution to the problem of testing internal computations is to
<em>expose</em> them in the source syntax.  For example, to test that
an expression's type is computed as expected, one can write
(<a href="../in/t0228.cc"><tt>in/t0228.cc</tt></a>):
<pre>
  __checkType(sName, arr);
</pre>
and Elsa will test whether the types it gets for <tt>sName</tt> and
<tt>arr</tt> are identical, and fail if they are not.

<p>
As a more interesting example, one can write
(<a href="../in/t0117.cc"><tt>in/t0117.cc</tt></a>):
<pre>
  __getStandardConversion((Derived *)0, (Base const *)0, SC_PTR_CONV|SC_QUAL_CONV);
</pre>
and Elsa will attempt to convert <tt>Derived*</tt> to <tt>Base const *</tt>,
and check that the conversion is a "pointer conversion" and a
"qualification conversion" (terms defined in the C++ standard).

<p>
This approach ensures we can write robust tests for any feature, even those
not directly connected to accepting or rejecting the input.
The set of all such special functions is defined in the
<tt>internalTestingHooks()</tt> function in
<a href="../cc_tcheck.cc"><tt>cc_tcheck.cc</tt></a>.

<a name="large_packages"></a>
<h3>7.1.4 Running Elsa on large software packages</h3>

<p>
Typically, Elsa users want to use Elsa to parse some specific piece
of software.  This requires some method for hooking into the build
process to obtain all of the preprocessed input files.

<p>
One very simple method is to use the
<a href="../test-parse-buildlog"><tt>test-parse-buildlog</tt></a>
script.  Just build the package normally (say, with gcc), saving
all of the output from <tt>make</tt> to a file.  Then this script
will read that file and use it to generate the preprocessed source
files one at a time, feeding each to <tt>ccparse</tt>.  This works
pretty well if the goal is to ensure that Elsa can parse a given
codebase.

<p>
However, it is not perfectly reliable (what if <tt>make</tt> is not
echoing all of its commands, or if the package does not use
<tt>make</tt> at all?), and it does not know how the translation units
are assembled to form libraries and executables.  For that, we use the
<a href="http://build-interceptor.tigris.org/">build interceptor</a>
system.  This replaces the system compiler with a script that
squirrels away the invocation history, which can then be reconstructed
to get an accurate picture of how the project as a whole fits
together.  (Note that build interception is something that a number of
research groups have recently done.  You may want to google for some
alternatives.)

<p>
When building a large package, keep in mind that a significant fraction
of the preprocessed source will come from the headers of whatever
compiler is used to do the preprocessing, and the choice of which
headers to use can affect both Elsa's ability to parse the code and
your analysis' ability to reason about the results.  There are a number
of approaches:
<ul>
<li>Use the headers normally used to build the package, such as gcc-3
    headers.  The disadvantage is they may be more complex than the
    package really needs, unduly complicating parsing and analysis.
<li>Use headers from an older compiler, such as gcc-2.  Most packages
    will work with the older compiler, and those headers are much simpler.
<li>Use a custom set of cut-down headers.  Elsa includes a few such
    headers in the <a href="../include"><tt>elsa/include</tt></a>
    directory, and those may serve as a useful starting point.
<li>Do something completely independent, using something like
    <a href="http://www.stlport.org/">STLport</a>.
</ul>


<a name="debugging"></a>
<h2>7.2 Debugging</h2>

<!--
debugging

  - tracing flags
    - a good set of flags to start with
  - toString(), gdb()
-->

<p>
Debugging is the process of mapping from evidence of a defect back to
the defect itself, such as an erroneous line of code.  Elsa has
some features specifically designed to assist during debugging.

<a name="tracing_flags"></a>
<h3>7.2.1 Tracing Flags</h3>

<p>
A generalization of <tt>printf</tt>-debugging, tracing flags let
the user control exactly what kind of information is printed, by
associating each debugging output command with a flag that must
be enabled for that output to be seen.  This is all implemented
by the
<a href="../../smbase/trace.html"><tt>trace</tt></a>
module in 
<a href="../../smbase/index.html">smbase</a>.

<p>
Though there are many tracing flags (grep for <tt>trace</tt> in the source
to find some), there is a set of flags that have become my standard
set of flags to use when debugging a minimized input file:
<ul>

<li><tt>error</tt>:
    Print every error message that is added to the list of errors
    in Env (<a href="../cc_env.h"><tt>cc_env.h</tt></a>).  This is useful
    for seeing when a particular message is added.  Note that some
    errors are added but never displayed, as part of disambiguation activity.

<li><tt>overload</tt>:
    Print details on the process of each overload resolution, such as
    the argument types, candidate functions, argument conversions, etc.

<li><tt>dependent</tt>:
    Show information about non-dependent lookups in templates.

<li><tt>template</tt>:
    Show basic template-processing information, in particular the
    instantiation activity.

<li><tt>templateXfer</tt>:
    This shows activities related to one of the most complex parts of
    template instantiation, the transferring of template-ness from
    members of templates to members of instantiations.

<li><tt>topform</tt>:
    Print a header for each toplevel form.  This helps to coordinate
    the debugging output with the input syntax.

<li><tt>matchtype</tt>:
    Print the arguments and result of each call into the type matcher,
    which is central to template argument deduction and template
    declaration matching.

<li><tt>templateParams</tt>:
    Print activity related to adding and removing template parameters
    to and from the scope stack, including the scope delegation
    mechanism (a dirty hack).

</ul>

<p>
To get these enabled automatically, I use a <tt>.gdbinit</tt> with
the following contents (<tt>tmp2.cc</tt> is the filename I typically use for
the testcase I'm currently working on):
<pre>
  file ccparse
  set args -tr error,overload,dependent,template,templateXfer,topform,matchtype,templateParams tmp2.cc
  set print static-members off
  break main
  break breaker
  run
</pre>

<p>
<b>Note:</b> Because they are rather expensive, none of the tracing
flags do anything unless Elsa has been <tt>./configure</tt>d with the
<tt>-debug</tt> switch.

<a name="data_print"></a>
<h3>7.2.2 Data structure print routines</h3>

<p>
While running Elsa in a debugger, it is often convenient to be able to
print values of variables.  Of course, if the variable is a primitive
type, then
<pre>
  (gdb) print x
</pre>
will suffice.  If <tt>x</tt> is not a primitive, then there is probably
a routine that can be invoked to print it, typically one of the following
forms:
<pre>
  (gdb) print toString(x)
  (gdb) print x->toString()
  (gdb) print x->asString()
  (gdb) print x->gdb()
</pre>
There is some rationale for the inconsistency, but I don't feel like
getting into all that here.  You will probably have to look at the
declaration of the associated type to find out which to use.

<a name="documentation"></a>
<h2>7.3 Documentation</h2>

<!--
documentation

  - external module docs
  - in the code
    - data member descriptions
    - function descriptions
    - paragraph style of coding
    - references to the standard
    - references to specific test cases
  - why no doxygen
-->

<a name="doc_external"></a>
<h3>7.3.1 External Documentation</h3>

<p>
The intent of the external documentation is to serve as something
of a roadmap to Elsa, to inform programmers of where things are
implemented and the assumptions behind those implementations.
By "external", I mean "not in the source code".

<p>
Each of the four major components of Elsa
(<a href="../../smbase/index.html">smbase</a>,
<a href="../../ast/index.html">ast</a>,
<a href="../../elkhound/index.html">elkhound</a> and
<a href="../index.html">elsa</a>)
has a page documenting it and containing a brief description
of its modules.  They also have dependency diagrams to express
some module interrelationships.

<p>
Further, some modules have their own documentation pages,
such as <a href="cc_type.html">cc_type.html</a> and
<a href="cc.ast.html">cc.ast.html</a>.  These pages explain
high-level aspects of the module's design and interaction with
other modules.  They are also linked from the index.html page
of the component.

<p>
Finally, there are some documents (e.g., <a href="lookup.txt">lookup.txt</a>)
that cut across modules, describing some or other C++ language
feature and its implementation in Elsa.

<a name="doc_internal"></a>
<h3>7.3.2 Internal Documentation</h3>

<p>
The source code contains a great deal of documentation in the form of
comments.  The comments are invaluable for quickly comprehending
pieces of code.  I'd rather lose the code than the comments.

<p>
The following paragraphs explain some of the commenting style used
(and to be used) in Elsa.  Perhaps I should make a separate style guide...

<p>
<b>Every data member of every class has a comment.</b>  There are no
exceptions.  The data members are a shared API among all the code that
can see them.  It is essential that the meaning and purpose of each
data member be clearly stated next to its declaration.  Example:
<pre>
  // nesting level of disambiguation passes; 0 means not disambiguating;
  // this is used for certain kinds of error reporting and suppression
  int disambiguationNestingLevel;
</pre>

<p>
<b>Most functions have a descriptive comment.</b>  The comment can be
associated with the declaration or the definition, depending on whether
most call sites are from outside or inside the module.  A function's
comment should indicate the meaning of parameters and return values,
and indicate the context in which it is called if that is relevant.
Example:
<pre>
  // Remove all scopes that are inside 'bound' from 'scopes' and put them
  // into 'dest' instead, in reverse order (to make it easy to undo).
  void Env::removeScopesInside(ObjList&lt;Scope&gt; &amp;dest, Scope *bound)
  { /*...*/ }
</pre>

<p>
<b>Group statements into paragraphs.</b>  Long sequences of imperative
code should be organized into small blocks ("paragraphs") of related functionality,
with a comment at the start saying the intent of that block, and blocks
separated by blank lines.  Example:
<pre>
  // connect tab A to slot B
  Tab *a = assembly.getTabA();
  Slot *b = widgetFoo.leftSlot;
  a-&gt;insertInto(b);

  // now fold it in half
  Polygon p = assembly.bisection();
  xassert(p.closed());
  FoldManager::singleton()-&gt;fold(assembly, p);

  // and queue for boxing
  boxQueue.enqueue(assembly);
</pre>

<p>
<b>Do not duplicate comments</b> for the same reason you do not
duplicate code.  If you must copy code, and it contains a comment,
delete the comment in the copy, possibly replacing it with something
like "as above".

<p>
<b>Make liberal references to the standard.</b>  Pointers into the
standard are very useful, for fairly obvious reasons.  On the other
hand, do not quote large pieces of it, as that merely clutters the
code.

<p>
<b>Make liberal references to the regression testcases.</b>  Most
of the time, if a bug is fixed, a comment near the fix should mention
the name of a testcase that demonstrates the bug.  This helps to
understand the code, since it provides a concrete example, and it
makes testing related modifications easier because you know to test
against the named testcases first.

<a name="doc_doxygen"></a>
<h3>7.3.3 Why I don't use Documentation Generators</h3>

<p>
Given the above discussion of documentation, it is reasonable to
ask why I do not advocate the use of "documentation generators"
such as <a href="http://www.stack.nl/~dimitri/doxygen/">doxygen</a>.
The main reason is I prefer not to have extra layers between
the artifact I edit and the artifact I read.  Extra layers mean more
work to map across them, and they make it less likely that the
documentation will be consulted and updated.

<p>
For documenting detailed behavior of the code, having the
documentation right in the code means it is immediately available,
and easy to update.  For those times when I want to use special
formatting or hyperlinks, I write a comment pointing at one of the
separate HTML documents and put the formatting there.

<p>
For documenting archtecture-level behavior, a separate HTML file like
this document works well.  I wouldn't want this to be a great big
doxygen comment.  Nor do I want to use any of the latex-to-HTML
translators, again for the reason of not wanting to introduce layers.
I expect most people would read documentation like this in their
web browser, not on paper, so producing postscript is not much benefit.

<p>
Finally, I feel that documentation generators can often be a
distracting influence, as programmers can begin to act as if
all that is needed to adequately document their code is to provide
(say) doxygen attributes X, Y and Z; when in fact, the essence of
good documentation is <em>communication</em> and <em>substance</em>,
not form.  


<a name="assertions"></a>
<h2>7.4 Assertions</h2>

<!--
assertions

  - rationale: ensure bugs have small witnesses
  - xassert, xassertdb
  - put a comment if the rationale for an assertion is not obvious
-->

<p>
I am a believer in assertions.  Their primary value is as part
of the specification of the program, providing a formal language
for codifying programmer assumptions.

<p>
Additionally, the run-time checking implied by an assertion serves to
aid testing and debugging by helping to ensure that <em>bugs have
small witnesses</em>.  That is, given a particular bug in the program,
the size of the input testcase required to demonstrate that bug is
smaller when the program contains good assertions, and larger when it
does not, because a failed assertion is an early manifestation of the
defect.  By reducing the size of the input required to witness a bug,
a given level of testing effort will find more bugs, and make the
program consequently more reliable.

<p>
When an assertion is added to the code, if it is not obvious from
inspection of the surrounding code why the condition should be true,
add a comment explaining it.  Someday your assertion <em>will</em>
fail, and when it does, you want to help the person who will have
to figure out what has gone wrong and that the impact of that is.
Example:
<pre>
  xassert(secondLast->qualifier);   // grammar should ensure this
</pre>

<p>
Within elsa, there are three main assertion-related functions,
defined in <a href="../../smbase/xassert.h">xassert.h</a>:
<ul>
<li><tt>xassert(cond)</tt>: Each time it is encountered, <tt>cond</tt> is
evaluated.  If <tt>cond</tt> is false, the <tt>x_assert</tt> assertion
(<a href="../../smbase/exc.h">exc.h</a>) is thrown.  Normally, this
exception is only caught by <tt>main()</tt>, so it is similar to the
C library's <tt>assert</tt>, which calls <tt>abort()</tt>.  However,
in Elsa's <tt>ccparse</tt> driver program, a exception handler prints out
the current location stack before aborting, often giving a clue as to
what has caused the failure.

<li><tt>xassertdb(cond)</tt>: This is like <tt>xassert</tt>, except it
is compiled away if <TT>NDEBUG</TT> is defined.  It is used for checks
that may significantly affect performance.

<li><tt>xfailure(msg)</tt>: This is always throws <tt>x_assert</tt>,
with the given message.  It is often used in code paths that are
believed to not be reachable.
</ul>


<a name="invalid_input"></a>
<h2>7.5 Invalid C++</h2>

<!--
attempts to reject invalid code

  - role in finding Elsa bugs faster
  - replicating other compilers' bugs
-->

<p>
As mentioned at the top of this document, Elsa does not try to reject
every invalid C++ program.  We tacitly assume that the programs Elsa
is asked to parse are <em>already</em> accepted by some C++ compiler,
which hopefully enforces the language.  However, enforcing some of the
language's rules can help to expose bugs.

<p>
Anecdote: For a long time, Elsa would only try to convert argument
types to parameter types if the function being invoked was overloaded.
Checking the conversions is of course necessary to do overload
resolution, but if the function is not overloaded then I figured it
wasn't necessary.  But the effect of this was that bugs in the type
computation logic would only be revealed in circumstances where overloading
was involved, meaning the testcases were complicated.  When I went ahead
and implemented checking for all function calls, at first there were a
bunch of bugs that were revealed and had to be fixed, but from then on
type computation bugs tended to have very simple witnesses, making it
fairly easy to fix them.  Lesson learned.

<p>
But to the extent Elsa does try to enforce the rules of the language,
there is another problem: sometimes it properly rejects inputs that
another compiler mistakenly accepts!  In that case we may need to add
a flag to CCLang (<a href="../cc_lang.h">cc_lang.h</a>) to emulate 
the bug.

<p>
However, we don't want to commit to emulating every bug in every
compiler.  Currently, our main goal is being able to parse code
compiled with gcc on Linux, so we will support a bug if:
<ul>
<li>the bug is present in the latest 3.x version of gcc, and
<li>the bug is also present in the latest Intel C++ compiler ("icc") or
    there is a lot of code in the wild that relies on the bug
</ul>
or, if
<ul>
<li>it's a gcc-2 bug and the gcc-2 headers need it
</ul>

<p>
Rationale: If the bug is not present in gcc-3.x, then presumably the
author of the code needing the bug is already under pressure to
fix it since the all the major Linux distributions are using gcc-3.
If the bug is not emulated by icc, and code needing it is rare, then we
can file a bug report directly with the package author, explaining that the
code is invalid and using icc to support that claim (icc is freely
available and reasonably popular).  Finally, we want to give users the
option of preprocessing their code with the gcc-2 headers (because
they are so much simpler), so we want to accept the code in those
headers.

<p>
For the case of bugs in the gcc-2 headers, rather than implement
full gcc-2 compatibility, I've just been adding little hacks that
look at the names of the identifiers involved before relaxing the
rules.  This way I minimize the degradation of the language
enforcement, while still accepting the code in those specific headers.











<p>
  <a href="http://validator.w3.org/check/referer"><img border="0"
      src="valid-html401.png"
      alt="Valid HTML 4.01!" height="31" width="88"></a>
</p>















<!-- the following exists to make sure the document has lots of space
     at the end, so that clicking on a link that points into the document
     will always put the referred-to section at the top of the browser
     window; without this, sections near the end don't work -->
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
<center>this space left intentionally blank</center>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>
&nbsp;<br>



</body>
</html>
